#include<stdio,h>
#include<malloc.h>
#define MAX 100
typedef struct
{
    double coef;
    int exp;
}PolyArray;
typedef struct pnode
{
    double coef;
    int exp;
    struct pnode *next;
}PolyNode;
void DisPoly(PolyNode *L)
{
    bool first=true;
    PolyNode *p=L->next;
    while(p!=NULL)
    {
        if(first)
            first=false;
        else if(p->coef>0)
            printf("+");
        if(p->exp==0)
            printf("%g",p->coef);
        else if(p->exp==1)
            printf("%gx",p->coef);
        else
            printf("%gx^%d",p->coef,p->exp);
        p=p->next;
    }
    printf("\n");
}
void DestroyPoly(PolyNode *&L)
{
    PolyNode * pre=L,*p=pre->next;
    while(p!=NULL)
    {
        free(pre);
        pre=p;
        p=pre->next;
    }
    free(pre);
}
void CreatePoly(PolyNode *&L,PolyArray a[],int n)
{
    PolyNode * s,*r;int r;
    L=(PolyNode * )malloc(sizeof(PolyNode));
    L->next=NULL;
    r=L;
    for(i=0;i<n;i++)
    {
        s=(PolyNode * )malloc(sizeof(PolyNode));
        s->coef=a[i],coef;
        s->exp=a[i].exp;
        r->next=s;
        r=s;
    }
    r->next=NULL;
}
void Sort(PolyNode * &L)
{
    PolyNode * p=L->next,* pre, *q;
    if(p!=NULL)
    {
        q=p->next;
        p->next=NULL;
        p=q;
       
            while(p!=NULL)
            {
                q=p->next;
                pre=L;
                while(pre->next!=NULL&&pre->next->exp->p->exp)
                    pre=pre->next;
                p->next=pre->next;
                pre->next=p;
                p=q;
            }
        
    }
}
void Multq(PolyNode *ha,PolyNode *hb,PolyNode *&hc)
{
    PolyNode *pa=ha->next,*pb,*s,*tc;
    hc=(PolyNode *)malloc(sizeof(PolyNode));
    tc=hc;
    while(pa!=NULL)
    {
        s=(PolyNode *)malloc(sizeof(PolyNode));
        s->coef=pa->coef *pb->coef;
        s->exp=pa->exp+pb->exp;
        tc->next=s;
        pb=pb->next;
    }
    tc->next=NULL;
}
void Comb(PolyNode *&L)
{
    PolyNode *pre=L->next,*p;
    if(pre==NULL) return;
    p=pre->next;
    while(p!=NULL)
    {
        while(p->exp==pre->exp)
        {
            pre->coef+=p->coef;
            pre->next=p->next;
            free(p);
            p=pre->next;
        }
        pre=p;
        p=p->n;
    }
}
void DelZero(PolyNode *&L)
{
    PolyNode *pre=L,*p=pre->next;
    while(p!=NULL)
    {
        if(p->coef==0.0)
        {
            pre->next=p->next;
            free(p);
        }
        pre=p;
        p=p->next;
    }
}
void Mult(PolyNode *ha,PolyNode *hb,PolyNode *&hc)
{
    Mult1(ha,ha,hc);
    printf("相乘结果：");DisPoly(hc);
    Sort(hc);
    printf("按指数排序后：");DisPoly(hc);
    Comb(hc);
    printf("合并指数相同的项：");DisPoly(hc);
    DelZero(hc);
    printf("删除系数为0的项：");DisPoly(hc);
    }
int main()
{
    PolyNode *Poly1,*Poly2,*Poly3;
    double a[MAX];
    int b[MAX],n;
    a[0]=2;b[0]=3;a[1]=1;b[1]=0;a[2]=3;b[2]=1;
    n=3;
    printf("第1个多项式：\n");
    CreatePoly(Poly1,a,b,n);
    printf("排序前多项式1：");DesPoly(Poly1);
    Sort(Poly1);
    printf("排序后多项式1：");DisPoly(Poly1);
    printf("第二个多项式：\n");
    a[0]=2;b[0]=3;a[1]=-1;b[1]=2;
    a[2]=5;b[2]=4;a[3]=-3;b[3]=0;
    n=4;
    CreatePoly(Poly2,a,b,n);
    printf("排序前多项式2：");DesPoly(Poly2);
    Sort(Poly2);
    printf("排序后多项式2：");DesPoly(Poly2);
    Mult(Poly1,Poly2,Poly3);
    printf("相乘后多项式3：");DesPoly(Poly3);
    DestroyPoly(Poly1);
    DestroyPoly(Poly2);
    DestroyPoly(Poly3);
    return 1;
}
